// 在 N * N 的网格中，我们放置了一些与 x，y，z 三轴对齐的 1 * 1 * 1 立方体。

// 每个值 v = grid[i][j] 表示 v 个正方体叠放在单元格 (i, j) 上。

// 现在，我们查看这些立方体在 xy、yz 和 zx 平面上的投影。

// 投影就像影子，将三维形体映射到一个二维平面上。

// 在这里，从顶部、前面和侧面看立方体时，我们会看到“影子”。

// 返回所有三个投影的总面积。

 


// 示例 1：

// 输入：[[2]]
// 输出：5


// 示例 2：

// 输入：[[1,2],[3,4]]
// 输出：17
// 解释：
// 这里有该形体在三个轴对齐平面上的三个投影(“阴影部分”)。



// 示例 3：

// 输入：[[1,0],[0,2]]
// 输出：8


// 示例 4：

// 输入：[[1,1,1],[1,0,1],[1,1,1]]
// 输出：14


// 示例 5：

// 输入：[[2,2,2],[2,1,2],[2,2,2]]
// 输出：21


 

// 提示：


// 	1 <= grid.length = grid[0].length <= 50
// 	0 <= grid[i][j] <= 50

# include <vector>

using namespace std;

class Solution {
public:
    int projectionArea(vector<vector<int>>& grid) {
        int n = grid[0].size();
        int res{0};
        for (int i{0}; i < n; ++i) {
            int rowMax{0}; // 行最大值
            int colMax{0}; // 列最大值
            for (int j{0}; j < n; ++j) {
                if (grid[i][j] > 0) ++res; // xy面

                // 小技巧
                rowMax = max(rowMax, grid[i][j]);
                colMax = max(colMax, grid[j][i]);
            }
            res += rowMax + colMax;
        }
        return res;
    }
};

#include "../stdc++.h"

class Solution {
public:
    int projectionArea(vector<vector<int>>& grid) {
        if (grid[0].empty() || grid[0].empty()) {
            return 0;
        }
        int m = grid.size();
        int n = grid[0].size();
        vector<int> rowMax(m, 0);
        vector<int> colMax(n, 0);
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0) {
                    ++res; // xy面投影面积加一
                    rowMax[i] = max(rowMax[i], grid[i][j]);
                    colMax[j] = max(colMax[j], grid[i][j]);
                }
            }
        }
        res += accumulate(rowMax.begin(), rowMax.end(), 0) + accumulate(colMax.begin(), colMax.end(), 0);
        return res;
    }
};
